package com.lxl.quick;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @Classname Classify
 * @Description 分类问题
 * @Date 2021/8/19 11:14
 * @Created by LXLDEMO
 */
public class Classify {
    public static void main(String[] args) {
        // 测试数据
        int arr[] = {2,1,1,1,4,8,1,6,5};
        partition(arr,3);
    }

    /**
     * 分类
     * @param arr
     * @param pivot 分界值
     * @return
     */
    public static int partition(int[] arr,int pivot){

        System.out.println("分界值 [" + pivot + "]");
        System.out.println("初始数据 " + Arrays.toString(arr)+"\n");

        int i = -1; // 用于记录比pivot小的值的下标
        int j = 0; // 用于遍历
        for (;j<arr.length;j++){
            // 只要比pivot小就和arr[i]交换
            if (j<arr.length && arr[j]<=pivot){
                swap(arr,i+1,j);
                i++;
                System.out.println("第"+(i+1)+"次交换结果 " +Arrays.toString(arr));
            }
        }



        System.out.println("最终结果 " + Arrays.toString(arr)+"\n");
        // 以下代码用于打印结果
        System.out.println("前"+(i+1)+"个为小于等于"+pivot+"的元素");
        System.out.println(pivot+"之前:");
        System.out.print("[ ");
        for (int n =0;n<=i;n++){
            System.out.print(arr[n] + " ");
        }
        System.out.print("]");

        System.out.println("\n"+pivot+"之后:");
        System.out.print("[ ");
        for (int n =i+1;n<arr.length;n++){
            System.out.print(arr[n] + " ");
        }
        System.out.println("]");
        return i;
    }

    /**
     * 交换函数
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr,int i ,int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

}
